class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) 
    {
        if (nums.size()<4)
            return {};        
        sort(nums.begin(),nums.end());
        vector<vector<int>> ret;
        for (int i=0;i<=nums.size()-4;)
        {
            for (int j=i+1;j<=nums.size()-3;)
            {
                int left=j+1;
                int right=nums.size()-1;
                while (left<right)
                {
                    long long sum=nums[i]+nums[j];
                    sum+=nums[left]+nums[right];
                    if (sum>target)
                        right--;
                    else if (sum<target)
                        left++;
                    else//sum==target
                    {
                        ret.push_back({nums[i],nums[j],nums[left],nums[right]});
                        left++;
                        while (nums[left]==nums[left-1]&&left<right)
                            left++;
                        right--;
                        while (nums[right]==nums[right+1]&&left<right)
                            right--;
                    }
                }
                j++;
                while (nums[j]==nums[j-1]&&j<=nums.size()-3)
                    j++;
            }
            i++;
            while (nums[i]==nums[i-1]&&i<=nums.size()-4)
                i++;
        }
        return ret;
    }
};
